package com.arron.algorithm.leetcodetop100.二分查找;


/**
 * 33. 搜索旋转排序数组
 */
public class 搜索旋转排序数组 {

    /**
     *  思路：
     *  1，每次找到中间节点，
     *  2，判断左右区间 ，判断哪个区间是有序区间
     *      如果左边是有序区间，则判断target值是否在此区间,则按照二分法不断查找
     *      如果不在左边，则将区间缩小到右边无序区间查找，
     *   3，在区间不断缩小的过程中，区间都会落到有序区间
     * @param nums
     * @param target
     * @return
     */

    public int search(int[] nums, int target) {

        if (nums.length == 1){
            return nums[0] == target? 0: -1;
        }
        int left = 0,right = nums.length-1;

        while (left<= right){

            int mid = left+(right-left)/2;

            if (nums[left] == target) return left;
            if (nums[right] == target) return right;
            if (nums[mid] == target) return mid;

            if (nums[left] < nums[mid]){
                //则说明左区间是有序的
                if (nums[left]<target && target< nums[mid]){
                    left= left+1;
                    right = mid -1;
                }else {
                    left = mid+1;
                }

            }else {
                //右区间是有序，直接判断是否在右边区间
                if (nums[mid]<target && target< nums[right]){
                    left = mid+1;
                    right = right-1;
                }else {
                    right = mid-1;
                }

            }
        }

        return -1;
    }



}
